package leetcode_top;

import java.util.*;
import org.junit.*;

import utils.BracketUtils;

public class Ex329 {
    class Solution1 {
        Map<String, Integer> map = new HashMap<>();
        int[][] matrix;
        boolean[][] flag;

        public int longestIncreasingPath(int[][] matrix) {
            this.matrix = matrix;
            this.flag = new boolean[matrix.length][matrix[0].length];
            int max = 1;
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[0].length; j++) {
                    max = Math.max(max, max(i, j, Integer.MIN_VALUE));
                }
            }
            return max;
        }

        public int max(int i, int j, int last) {
            String key = i + "_" + j;
            if (!inArea(i, j) || flag[i][j] || matrix[i][j] <= last) {
                return 0;
            }
            if (map.containsKey(key)) {
                return map.get(key);
            }
            flag[i][j] = true;

            int up = max(i + 1, j, matrix[i][j]);
            int down = max(i, j + 1, matrix[i][j]);
            int left = max(i - 1, j, matrix[i][j]);
            int right = max(i, j - 1, matrix[i][j]);

            flag[i][j] = false;
            int max = Math.max(Math.max(up, down), Math.max(left, right)) + 1;
            map.put(key, max);
            return max;
        }

        public boolean inArea(int i, int j) {
            return i >= 0 && i < matrix.length && j >= 0 && j < matrix[0].length;
        }
    }

    class Solution {

        int[][] matrix;
        public int longestIncreasingPath(int[][] matrix) {
            int m = matrix.length, n = matrix[0].length;
            this.matrix = matrix;
            Queue<int[]> queue = new LinkedList<>();
            int[][] outDegrees = new int[m][n];
            boolean[] cur;

            //计算每个节点的出度
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    cur = findBigger(i, j);
                    for (boolean b: cur) {
                        if (b) outDegrees[i][j]++;
                    }
                }
            }

            //初始加入0出度节点
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (outDegrees[i][j] == 0) queue.offer(new int[]{i, j});
                }
            }
            int[][] mov = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
            int times = 0, k, x, y;
            int[] arr;
            //本来出度为0的点(较大点是旁边的较小点的依靠，现在将0出度出队，含义就是那些点可能没办法有一个走的方向了，因此出度要减少)
            while (!queue.isEmpty()) {
                k = queue.size();
                ++times;
                for (int i = 0; i < k; i++) {
                    arr = queue.poll();
                    for (int[] t: mov) {
                        x = arr[0] + t[0];
                        y = arr[1] + t[1];
                        if (inArea(x, y) && matrix[x][y] < matrix[arr[0]][arr[1]]) {
                            outDegrees[x][y]--;
                            if (outDegrees[x][y] == 0) {
                                queue.offer(new int[]{x, y});
                            }
                        }
                    }
                }
            }
            //最后能够出度的轮数就是最终的答案
            return times;
        }

        public boolean[] findBigger(int i, int j) {
            boolean up = inArea(i + 1, j) && matrix[i + 1][j] > matrix[i][j];
            boolean down = inArea(i, j + 1) && matrix[i][j + 1] > matrix[i][j];
            boolean left = inArea(i - 1, j) && matrix[i - 1][j] > matrix[i][j];
            boolean right = inArea(i, j - 1) && matrix[i][j - 1] > matrix[i][j];
            return new boolean[]{up, down, left, right};
        }

        public boolean inArea(int i, int j) {
            return i >= 0 && i < matrix.length && j >= 0 && j < matrix[0].length;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        int[][] mat = BracketUtils.to2DArray("[[9,9,4],[6,6,8],[2,1,1]]");
        System.out.println(s.longestIncreasingPath(mat));
    }
}
